Polar codes define a new class of channel codes, which were introduced by Arikan in his seminal work “Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels”, IEEE Trans. Inform. Theory, July 2009. Polar codes are capacity-achieving over various classes of channels under encoding and decoding complexity of order O(N log N) in the code length N which was a break-through in coding theory. These codes have remarkable performance for practical finite code lengths as well. The state-of-the-art decoder uses successive cancellation (SC) decoding, as described in the above mentioned work of Arikan, in connection with list decoding (e. g., Tal and A. Vardy in “List decoding of polar codes,” in IEEE ISIT July 2011) and possibly an additional cyclic-redundancy-check (CRC) to improve the distance properties of the code and to improve the list decoding (e. g., Kai Niu and Kai Chen, “CRC-Aided Decoding of Polar Codes”, IEEE Commun. Letters, vol. 16, no. 10, October 2012).
According to their initial construction, polar codes have lengths N that are powers of two, i.e. N=2n, where n is an integer. However, recent works have proposed ways to puncture or shorten polar codes of length N in order to achieve any code length N′ (N≠N′). Therefore, any code rate R, wherein R=K/N, K being the number of information bits, is possible. In practical deployments, a CRC is applied to the K information bits. This CRC significantly improves the code properties, and is also exploited in the decoding process.
A (N, K) polar code, where N=2n, is defined by the following matrix:
            F      n        =                  [                                            1                                      0                                                          1                                      1                                      ]                    ⊗        n              ,wherein ⊗ n denotes the n-fold Kronecker product of the 2×2 base matrix
      [                            1                          0                                      1                          1                      ]    ,and a frozen set F containing the indices of the frozen bits, which are not used for information transmission. The K information bits can be encoded using polar codes of length N either by means of non-systematic encoding or by means of systematic encoding.
FIG. 1(a) shows an example of non-systematic encoding of four information bits using a polar code of length eight, referred to as a (8, 4) polar code having a rate R=1/2, according to the above mentioned work of Arikan. In this figure, the mutual information I(Wi) of the so-called virtual channels for the bits ui is shown on the left-hand side. The mutual information I(Wi) expresses the bit-channel reliability: if it is close to one, than the channel is defined as a ‘good’ channel and can be used to transmit information bits. On the contrary, if I(Wi) is close to zero than the channel is defined as a ‘bad’ channel and it shouldn't be used to transmit information bits. Therefore, the four bit indices corresponding to the lowest values of the mutual information I(Wi) are collected into the set of frozen bit indices F={1, 2, 3, 5}, in order to obtain a code having a rate R=1/2. For encoding, the four information bits [u0 u1 u2 u3] are placed in the non-frozen position and the bits corresponding to the indices contained in the set of frozen bit indices F are set to zero. Through matrix multiplication the code bits [c0 c1 c2 c3 c4 c5 c6 c7] are obtained as follows:
            [                                    0                                0                                0                                              u                              0                ⁢                                                                           0                                              u              1                                                          u              2                                                          u              3                                          ]        ×                  [                                            1                                      0                                                          1                                      1                                      ]                    ⊗        3              =            [                                                  c              0                                                          c              1                                                          c              2                                                          c              3                                                          c              4                                                          c              5                                                          c              6                                                          c              7                                          ]        .  
FIG. 1(b) shows an example of systematic encoding of an (8, 4) polar code, wherein the systematic encoding can be achieved by a two-step scheme as illustrated in “Flexible and low-complexity encoding and decoding of systematic polar codes,” in arXiv:1507.03614 July 2015, by Sarkis et. al. The first step is identical to the one in non-systematic encoding. In the vector obtained after the first step, the frozen bits are again set to zero, and the non-systematic encoding is applied again. As a result, a systematic encoder is obtained and the information bits become the systematic bits in the code word (bits on the right). The sets of indices of frozen bits define the polar codes, hence their design is of paramount importance for the code performance.
In both the non-systematic encoder and the systematic encoder, a CRC may be applied to the vector of information bits, defined by [u0 u1 u2 u3] in the above mentioned example.
Concerning the decoding by means of polar codes, there are two main decoding algorithms: the successive cancellation (SC) decoding, as suggested in the above mentioned work by Arikan, and the list SC (LSC) decoding, as suggested in List Decoding of Polar Codes,” in IEEE ISIT July 2011 by Tal and A. Vardy and in “CRC-Aided Decoding of Polar Codes”, IEEE Commun. Letters, vol. 16, no. 10, October 2012 by Kai Niu and Kai Chen. The SC decoding scheme has extremely low complexity and is sufficient for very large code lengths N due to the polarization effect. For medium-length and short-length codes, the LSC decoding scheme is preferred due to the fact that it can efficiently deal with the error propagation of SC decoding. Furthermore, the LSC decoding scheme allows to decrease the decoding error rate by using longer lists. Thus it allows to trade performance versus complexity.
FIG. 2 shows the bit error rate as a function of the signal-to-noise-ration (SNR) in dB for different decoding schemes, in case of a binary phase shift keying—additive white Gaussian noise ((BPSK-AWGN) channel. In particular, it allows to compare the performance of a (2048, 1024) polar code using SC and LSC (L=32) decoding schemes to the performance of the state-of-the-art channel decoding schemes. This comparison shows that polar codes are a very powerful class of channel codes, and they can be expected to play an important role in future communication systems.
The original polar code construction allows for any code rate, by choosing the size of the frozen set. However, they allow only the construction of codes having lengths that are powers of 2, i.e., N=2n. The restriction of the length of the code is a major drawback of polar codes, which needs to be overcome for practical applications. Using the techniques of so-called puncturing and shortening from coding theory, the polar codes can be trimmed to any code length, as it will be explained in the following. In the following, polar codes of lengths N=2n will also be referred to as mother polar codes.
FIG. 3(a) illustrates the main idea of puncturing. In puncturing, one or more code bits are not transmitted. The decoder typically handles punctured bits as erased and applies the decoder of the mother polar code of length N. Puncturing has the benefit of making the code rate R more flexible and allows immediately for incremental redundancy, however it gives less control on the resulting distance properties. If a code of length N′ has to be created to encode K information bits with R=K/N′, then a mother (K, N) polar code is used to encode the data, with N>N′, and P=N−N′ bits are punctured. For decoding, the P punctured code bits are assigned log-likelihood ratios (LLR) of zero, and usual decoding of the mother polar code of length N is applied. Puncturing changes the code properties and the decoding behavior, therefore the positions to be punctured need to be carefully chosen.
FIG. 3(b) illustrates the main idea of shortening. In shortening, a sub-code of the mother polar code of length N is used in which one or more bits are restricted to a fixed value, typically zero. In the case of a systematic encoder, one or more systematic bits can be chosen for this purpose, and they can simply be set to zero in the encoding process. These fixed bits are not transmitted. At the decoder side, the shortened bits are known, their LLRs are set to very large values, and the decoder of the mother polar code of length N is applied. Shortening achieves the same code rate flexibility as puncturing, however with more control over the code properties. If a code of length N′ has to be created to encode K information bits, the data is initially padded with S=N−N′ zeros (also called the shortening bits), and a (N, K+S) mother polar code is chosen with N>N′. The obtained K+S information bits and shortening bits are encoded using a systematic polar encoder. Before transmission the S shortening bits are removed. This procedure preserves the minimum distance of the mother polar code and thus provides more control over the code properties than puncturing. At the decoder side, the S removed bits are known to be zero. Correspondingly the LLRs of these code bits are initialized with large positive values (in theory with infinity). Afterwards, usual decoding of the mother polar code of length N is applied.
In both puncturing and shortening, the selection of the bit positions to puncture or shorten is of paramount importance in the mother polar code design in order to obtain good error-rate performance.
In the conventional art several solutions are provided in order to design sets of frozen bit indices, sets of puncturing bit indices and sets of shortening bit indices. These solutions can be divided into three categories: optimal puncturing/shortening pattern generation, optimal frozen set generation and joint optimization, as will be described in the following.
The optimal puncturing or shortening pattern generation technique deals with finding the optimal puncturing or shortening patterns once the frozen sets of the mother polar code are given. This technique is used in the work “On the Puncturing Patterns for Punctured Polar Codes”, IEEE ISIT July 2014, by Zhang et. al, to create a punctured polar code. In particular, the less reliable bits are selected to be frozen, and an algorithm is run to find an optimal puncturing pattern leading to the selected frozen bits. The error-rate performance of this technique is sub-optimal compared to other ones, but the puncturing pattern is less complex to compute. Still, the optimization algorithm has to be run every time a (N, K) polar code has to be generated. This increases the latency of the system, which is a disadvantage of this approach.
The optimal frozen set generation technique deals with finding the optimal frozen set once the puncturing or shortening pattern is given. This technique is proposed for shortening of non-systematic polar codes in the work “A Novel Puncturing Scheme for Polar Codes”, IEEE Commun. Letters, December 2014, by Wang et. al, while it is proposed for puncturing of non-systematic polar codes in the works “Design of Length-Compatible Polar Codes Based on the Reduction of Polarizing Matrices”, IEEE Trans. Commun., 2013, by Shin et. al. and “Beyond Turbo Codes: Rate-Compatible Punctured Polar Codes”, IEEE ICC June 2013 by C. Kai et al. In the above mentioned work by Wang et al., the shortening pattern is selected using the last bits of a (N, K) mother polar code. Similarly, in the above mentioned works by Shin et al. and by Kai et al., the puncturing pattern is generated according to a certain heuristic, and a density evolution (DE) algorithm is run to find the optimal frozen set given the puncturing pattern. The frozen set needs to be calculated at every encoding and every decoding, whenever the code is changed, and the DE algorithm is a relatively complex algorithm. Even though the error-rate performance of this technique is good, the high complexity and resulting latency due to the DE calculation makes this technique unattractive for practical implementations.
The joint optimization technique is presented for shortening of non-systematic polar codes in the work “Shortened Polar Codes”, IEEE Trans. Inform. Theo., September 2015 by V. Miloslavskaya. In this technique, the frozen set and the shortening pattern are jointly optimized. For a given (N′, K) code, a search over all possible shortening patterns is performed. The complexity of this full search can largely be reduced by exploiting certain symmetries of the polar encoder. The error-rate performance of this technique is good due to the optimal design. However, large amounts of memory are required for storing a table comprising the frozen set and the shortening pattern for every N′ and K. For practical applications that require large sets of code lengths N′ and code rates R, this method is not convenient.
Although the above mentioned techniques of the conventional art provide some solutions to the problem of designing codes having arbitrary lengths and rates by using polar codes, they all present disadvantages related to their practical implementations due to their high description complexity. One of the main disadvantages of existing techniques is the lack of structure in the generation of the frozen sets, the puncturing patterns and the shortening patterns. In particular, every (N′, K) code has a different frozen set and puncturing or shortening pattern, and for each pair (N′, K), these sets and patterns have to either be stored, requiring a large memory for storage, or be calculated on the fly, resulting in large computational complexity.
Therefore, there is a need for improved devices and methods implementing polar codes in communication systems.